package com.kingwood.algorithm.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/2/27 14:50
 * @Modified By：
 * @Version 1.0
 */
public class Zuhe {
    /**
     * 在数组中选取n个数进行组合（不考虑顺序且数据不重复）
     * @param arr 原数组
     * @param newarr 组合后得到的数组
     * @param k  从哪一个下标的元素开始取
     * @param n 需要取出元素的个数
     * */
    private static void combination(int[] arr,int[] newarr, int k, int n) {
        //当需要取出的元素个数是0时，说明组合完成
        if (n==0) {
            for (int i = 0; i < newarr.length; i++) {
                System.out.print(newarr[i]);
            }
            System.out.println();
            return;
        }

        for (int i = k; i <= arr.length-n; i++) {
            newarr[newarr.length-n] = arr[i];	//将提取出来的数依次放到新数组中
            combination(arr, newarr,i+1, n-1);	//按照同样的方法从剩下的元素中选出n-1个元素
        }
    }

    public static List<List<Integer>> resList = new ArrayList<>();

    /**
     * 游戏分组
     * https://fcqian.blog.csdn.net/article/details/134633477
     * *
     */
    public static int gameGroup(int[] arr) {
        Arrays.sort(arr);

        ArrayList<Integer> res = new ArrayList<>();

        dfs(arr, 0, 0, 0, res);

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        int min = Integer.MAX_VALUE;
        for (Integer subSum : res) {
            int curAbs = Math.abs((sum - subSum) - subSum);
            if (curAbs < min) {
                min = curAbs;
            }
        }

        return min;
    }

    public static void dfs(int[] arr, int index, int level, int sum, ArrayList<Integer> res) {
        if (level == 5) {
            res.add(sum);
            return;
        }

        for (int i = index; i < 10; i++) {
//            if (i > index && arr[i] == arr[i-1]) {
//                continue;
//            }
            dfs(arr, i+1, level+1, sum+arr[i], res);
        }
    }

    // 使用回溯算法生成所有的组合
    public static void backtrace(int[] arr, int start, List<Integer> combination) {
        if (combination.size() == 5) {
            resList.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            combination.add(arr[i]);
            backtrace(arr, i+1, combination);
            combination.remove(combination.size()-1);
        }
    }

    public static void main(String[] args) {
//        int[] arr = {1,2,3,4,5,6,7,8,9,10};
//        int[] newarr = new int[5];
//        combination(arr, newarr, 0, 5);

        Scanner scanner = new Scanner(System.in);
        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(gameGroup(arr));

        backtrace(arr, 0, new ArrayList<>());
        List<Integer> res = new ArrayList<>();
        int sum = Arrays.stream(arr).sum();
        for (List<Integer> list : resList) {
            int subSum = list.stream().mapToInt(Integer::intValue).sum();
            res.add(subSum);
        }

        int min = Integer.MAX_VALUE;
        for (Integer subSum : res) {
            int curAbs = Math.abs((sum - subSum) - subSum);
            if (curAbs < min) {
                min = curAbs;
            }
        }

        System.out.println(min);
    }
}
